COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00022 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a65.tex[106,phy] \today\hfill}

\bigskip
\line{\bf Recursion.\hfill}

How do you take the derivative of a long formula?  I break it into several
shorter formulas, take their derivatives, and combine the results.  If the 
formula is  $F=G/H$,  I~get $G'$ and $H'$ in separate calculations, then combine
them as  $F'=(G'H-H'G)/H↑2$.   The process, superficially, looks circular;
before I~can find one derivative, I~have to find another.  In fact the
subordinate derivations get easier and easier, acting on shorter formulae;
eventually all the subproblems reduce to finding derivatives of variables
or constants, which can be done directly.

An algorithm which solves problems by taking time out along the way to solve
simpler problems of the same kind, using the same methods, is called 
{\sl recursive\/}.
To execute such an algorithm, you must keep track separately of variables for
each subordinate problem, and of where you are in the instructions for each
subordinate problem.  For example, you could write each subordinate problem
on a separate sheet of paper, and cross reference the sheets to allow returning
from a subordinate problem to its parent problem.  As we shall see, Pascal
procedures and functions can be used to carry out recursive algorithms.

*******Insert adaptive integration algorithm.

Another recursive algorithm can be used to allow input of real numbers as
arbitrary arithmetic formulae built up from real constants.  For example,
if a program requires an input of a temperature measured in Celsius units,
and I~want to enter $98.6↑\circ$ Fahrenheit, it would be convenient to type
$\bigl((5\times (98.6-32))/9\bigr)$ 
rather than hand-calculating the converted value.  The
algorithm is this:

If the first character is `(', the input must be of the form ($F\, O\, G$), where
$F$ and $G$ are formulae (possibly simply numbers) and $O$ is one 
of $+$, $-$, $\times$, $/$.
Using the same algorithm, read $F$, getting a numerical value~$Y$; read the
operator $O$ and save it; read $G$, getting a numerical value~$Z$;
 read the~')';
depending on the operator character~$O$, return  $Y+Z$, $Y-Z$, 
$Y\times Z$, or $Y/Z$.
If the first character is not~(, read a number and return it.

In Pascal, this algorithm is expressed as a procedure:

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        PROCEDURE READFORM(VAR F:TEXT; VAR X: REAL);
        VAR Y,Z: REAL; OP: CHAR;
        BEGIN
        IF F$\uparrow$<>'(' THEN
            READ(F,X)
        ELSE
            BEGIN
            GET(F); (* DISCARD'(' *)
            READFORM(F,Y);
            READ(F,OP);
            READFORM(F,Z);
            IF F$\uparrow$<>')' THEN WRITE({\rm error message});
            GET(F);
            CASE OP OF (* FIX UP SYNTAX *)
                '+': X:=Y+Z;
                '-': X:=Y-Z;
                '*': X:=Y*Z;
                '/': X:=Y/Z END (* CASE *)
            END
        END
}

\smallskip
To see what the procedure does in detail, insert at the beginning and end of the
procedure body the commands

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        WRITELN('STARTING READFORM') {\rm{and}}
        WRITELN('LEAVING READFORM').
}

\smallskip\noindent
After each read, echo the input; after {\tt READFORM(F,Y)}, 
say, include the command

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        WRITELN('RESULT Y OF RECURSION', Y).
}

\smallskip\noindent
I recommend reading the output of executing this expanded procedure on several
formulae.

Next we look at how a recursive procedure can be executed by hand.  Suppose
[as in an earlier case study]
we have a character array, {\tt C[1..N,1..N]}, 
which contains a number of non-blank
regions, or blobs.  We say that two non-blank characters must belong to the
same blob if they are adjacent horizontally or vertically.  In this diagram,

\bigskip
{\tt
$$\vbox{\offinterlineskip
\halign{\strut#&\vrule#&$\;$\hfil#\hfil$\;$&\vrule#&$\;$\hfil#\hfil$\;$%
&\vrule#&$\;$\hfil#\hfil$\;$&\vrule#&$\;$\hfil#\hfil$\;$%
&\vrule#&$\;$\hfil#\hfil$\;$&\vrule#&$\;$\hfil#\hfil$\;$%
&\vrule#&$\;$\hfil#\hfil$\;$&\vrule#\cr
\multispan{15}\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&\phantom{A}&&\phantom{B}&&&&&&&&&&\phantom{A}&\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\multispan{15}\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&&&&&A&&B&&&&&&&\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\multispan{15}\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&&&&&C&&&&E&&F&&&\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\multispan{15}\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&&&&&D&&&&G&&H&&&\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\multispan{15}\hrulefill\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
&&&&&&\phantom{D}&&&&&&&&&\cr
\omit&height2pt&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&&\omit&\cr
\multispan{15}\hrulefill\cr
}}$$
}

\bigskip\noindent
{\tt ABCD} is one blob, {\tt EFGH} another.  
As part of a procedure to count the blobs in
a region, we want a procedure to check if there is a non-blank character in a
specified position, and if so, to erase the entire blob to which that character
belongs.

The algorithm to erase a blob at array coordinates {\tt X},{\tt Y} 
is readily expressed recursively:

\disleft 40pt:{}:
	If {\tt C[X,Y]} is blank, do nothing.
\disleft 40pt:{}:
	If {\tt C[X,Y]} is non-blank, make it blank and apply the same algorithm
	to the four adjacent points.

\smallskip\noindent
We assume there is a border of blanks around the picture to avoid going out
of bounds.

To show the algorithm is a correct one, we show it always halts, that it erases
everything connected to the original point, and that it erases nothing else.

The body of the algorithm has no iterations, so the algorithm could go on forever
only by creating infinitely many subproblems.  At each point, only the first
application of the algorithm to the point can create subproblems; later ones
find {\tt C[X,Y]} blank and immediately are finished.  Therefore at most 
{\tt N$↑2$} of the
applications can create subproblems, and at most $4{\tt N}↑2$
subproblems can be created.

If the point {\tt (U,V)} is 
initially in the same blob as {\tt (X,Y)}, there is a non-blank
path between them.  If the execution of the algorithm does not reach {\tt (U,V)},
there is a first place on the path it fails to reach.  But when it first
reaches the previous point on the path, that point is non-blank, and it creates
a subproblem at all four surrounding points; this would be a contradiction, so
the algorithm reaches all points of the blob.

The algorithm has no way to get outside the set of points consisting of the blob
itself and the blanks immediately adjacent to it, so it erases the blob, the
whole blob, and nothing but the blob.

In Pascal, the algorithm is expressed as:

\bigskip
{\obeylines\obeyspaces\let =\ \tt
        PROCEDURE ERASEAT(X,Y: INTEGER);
        BEGIN
        IF C[X,Y]<>' ' THEN
            BEGIN
            C[X,Y]:=' ';
            ERASEAT(X+1,Y); (* 1 *)
            ERASEAT(X-1,Y); (* 2 *)
            ERASEAT(X,Y+1); (* 3 *)
            ERASEAT(X,Y-1)
            END
        END
}

\bigskip
To execute by hand the application of the procedure by the call
{\tt ERASEAT(3,7)} on the array shown below,	

\smallskip
$$\vcenter{\offinterlineskip
\halign{\hfil${#}$\quad&\vrule#&\strut\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil%
&\xskip\hfil #\hfil\xskip&\vrule#\cr
Y =&\omit&1&2&3&4&5&6&7&8&9&10\cr
\noalign{\smallskip}
&\multispan{12}\hrulefill\cr
&height6pt&\multispan{10}&\cr
    X =	1&&\multispan{10}&\cr
&height6pt&\multispan{10}&\cr
	2&&\multispan{10}&\cr
&height6pt&\multispan{10}&\cr
	3&&\multispan6&*&*&&&\cr
&height6pt&\multispan{10}&\cr
	4&&\multispan6&*&&&&\cr
&height6pt&\multispan{10}&\cr
	5&&\multispan6&*&&&&\cr
&height6pt&\multispan{10}&\cr
	6&&\multispan{10}&\cr
&height6pt&\multispan{10}&\cr
	7&&\multispan{10}&\cr
&height6pt&\multispan{10}&\cr
	8&&\multispan{10}&\cr
&height6pt&\multispan{10}&\cr
	9&&\multispan{10}&\cr
&height6pt&\multispan{10}&\cr
       10&&\multispan{10}&\cr
&height6pt&\multispan{10}&\cr
&\multispan{12}\hrulefill\cr
}}$$


\medskip\noindent
we start by creating a contour box

\bigskip\halign{\qq\qq\lft{\tt #}\cr
	ERASEAT(3,7)\cr
\noalign{\smallskip}
	X=3\q	Y=7\q	{\rm Return to Main}\cr}



\bigskip\bigskip\noindent
showing the procedure being executed and the values of its arguments outside;
inside, current values of parameters, and where to return when finished are
recorded.  Executing the procedure body, we set {\tt C[3,7]} to blank, and make
another call on {\tt ERASEAT}, starting a new contour box; we now have:


\bigskip\halign{\qq\qq\lft{\tt #}\cr
	ERASEAT(3,7)\cr
\noalign{\smallskip}
	X=3\q	Y=7\q	{\rm Return to Main}\cr
\qq	ERASEAT(4,7)\cr
\noalign{\smallskip}
\qq	X=4\q	Y=7\q	{\rm Return to 1}\cr}


\bigskip\bigskip
\noindent
There are now two distinct variables, both called~{\tt X}, with different values.
One, with the value~4, is in current use; until we close the inner box, any
reference to {\tt X} is assumed to mean the inner one, so the next call,
{\tt ERASEAT(X+1,Y)} means {\tt ERASEAT(5,7)}.  
After completion of the second call, shown
by closing its box, reference to {\tt X} is assumed to mean the outer one, resuming
the previously interrupted procedure call where {\tt X} is~3.

After several more steps, the contours look like this, leaving out some
redundant information:

\bigskip\halign{\qq\qq\lft{\tt #}\cr
	ERASEAT(3,7)\cr
\noalign{\smallskip}
	X 3\q	Y 7\q	R {\rm Main}\cr
\qq	  {\rm erases} C[3,7]\cr
\noalign{\smallskip}
\qq	X 4\q	Y 7\q	R 1\cr
\qq\qq	  {\rm erases} C[4,7]\cr
\noalign{\smallskip}
\qq\qq	   X 5\q Y 7\q	R 1\cr
\qq\qq\qq    {\rm erases} C[5,7]\cr
\noalign{\smallskip}
\qq\qq\qq    X 6\q Y 7\q R 1\cr
\noalign{\smallskip}
\qq\qq\qq    X 4\q Y 7\q R 2\cr
\noalign{\smallskip}
\qq\qq\qq    X 5\q Y 8\q R 3\cr
\noalign{\smallskip}
\qq\qq\qq    X 5\q Y 6\q R 4\cr}

\bigskip\bigskip
\noindent
We return to the level where {\tt X=5}, {\tt Y=7}, 
at the point labelled {\tt (*~4~*)}, and find
it is finished; we close off the bottom of its box,

\figbox .7truein:

\noindent
and return to the level where {\tt X=4}, {\tt Y=7}, at {\tt (*~1~*)}

\bigskip\halign{\qq\qq\lft{\tt #}\cr
\qq\qq       X 3\q Y 7\q  R 2\cr
\noalign{\smallskip}
\qq\qq	     X 4\q Y 8\q R 3\cr
\noalign{\smallskip}
\qq\qq	     X 4\q Y 6\q R 4\cr}


\vfill\eject

\noindent
Now we are back at the original call, with {\tt X=3}, {\tt Y=7}, at 
{\tt (* 1 *)}

\bigskip\halign{\qq\qq\lft{\tt #}\cr
\qq	     X 2\q Y 7\q R 2\cr
\noalign{\medskip}
\qq	     X 3\q Y 8\q R 3\cr
\qq\qq	      {\rm erases} C[3,8]\cr
\noalign{\smallskip}
\qq\qq	      X 4\q  Y 8\q  R 1\cr
\noalign{\medskip}
\qq\qq	      X 2\q  Y 8\q  R 2\cr
\noalign{\medskip}
\qq\qq	      X 3\q  Y 9\q  R 3\cr
\noalign{\medskip}
\qq\qq	      X 3\q  Y 7\q  R 4\cr
\noalign{\bigskip}
\qq	    X 3\q  Y 6\q R 4\cr}

\bigskip\bigskip

Now we are back in the main program, having completed the execution of
{\tt ERASEAT(3,7)}.  The variables {\tt X} and~{\tt Y} 
no longer exist, as indicated by the
closing of all the boxes containing them.  The blob has been erased.

Naturally, computer execution of recursive procedures is not literally done by
drawing boxes.  It does involve keeping values for several variables of the
same name, and remembering the place in the program where
execution should return after each procedure call is finished.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft March 28, 1984

\bye